package com.hanxiaozhang.link.fastslowpointer;

import com.hanxiaozhang.link.singlylink.Node;

/**
 * 〈一句话功能简述〉<br>
 * 〈快慢指针相关算法题〉
 *
 * @author hanxinghua
 * @create 2022/3/17
 * @since 1.0.0
 */
public class FastSlowPointerTopic {

    public static void main(String[] args) {

        // 1->2->3->4->5->6->1
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);
        head.next.next.next.next.next.next = head;

        // 1->2->3 <- 8 <- 7
        //        \->       \ ->
        //         4        6
        //          \->   / ->
        //             5
        Node head1 = new Node(1);
        head1.next = new Node(2);
        Node node3 = new Node(3);
        head1.next.next = node3;
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next.next = new Node(8);
        head1.next.next.next.next.next.next.next.next = node3;


        // 1->2->3
        Node head2 = new Node(1);
        head2.next = new Node(2);
        head2.next.next = new Node(3);


        System.out.println(isRingNode(head2));
        System.out.println(RingNodeLength(head2));
        Node<Integer> node = getConnectNode(head2);
        System.out.println(node == null ? "null" : node.data);
        System.out.println(LinkLength(head2));
    }

    /**
     * 是否有环
     * <p>
     * 设置两个指针slow、fast，从头指针开始，每次分别前进1步、2步。
     * 如存在环，则两者相遇；如不存在环，fast遇到null退出。
     *
     * @param head
     * @return
     */
    private static boolean isRingNode(Node head) {

        if (head == null || head.next == null || head.next.next == null) {
            return false;
        }
        Node slow = head.next;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return false;
    }


    /**
     * 环的长度
     * <p>
     * 到问题1的碰撞点之后，从该点开始再一次快慢指针，再次碰撞所走过的操作数就是环的长度。
     * Tips：从该点开始再一次快慢指针。
     *
     * @param head
     * @return
     */
    private static int RingNodeLength(Node head) {
        int length = 0;
        if (head == null || head.next == null || head.next.next == null) {
            return length;
        }

        Node slow = head.next;
        Node fast = head.next.next;
        // 是否为已经第一次相遇表示标识
        boolean firstMeetedFlag = false;
        while (fast.next != null && fast.next.next != null) {
            // 快慢指针相遇
            if (slow == fast) {
                if (firstMeetedFlag) {
                    break;
                } else {
                    firstMeetedFlag = true;
                }
            }
            if (firstMeetedFlag) {
                length++;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return length;
    }


    /**
     * 获取连接点
     * <p>
     * 定理：碰撞点到连接点的距离 = 头指针到连接点的距离。
     * 因此，分别从头指针和碰撞点开始走，再相遇的那个点就是连接点。
     *
     * @param head
     * @return
     */
    private static Node<Integer> getConnectNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }

        Node slow = head.next;
        Node fast = head.next.next;
        boolean flag = false;
        while (fast.next != null && fast.next.next != null) {
            if (slow == fast) {
                flag = true;
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        if (!flag) {
            return null;
        }
        // 分别从头指针和碰撞点开始走，再相遇的那个点就是连接点。
        while (true) {
            if (head == slow) {
                return slow;
            }
            head = head.next;
            slow = slow.next;
        }
    }

    /**
     * 带环链表的长度是多少
     * <p>
     * 带环链表的长度 = 问题3中连接点距离头指针的长度 + 问题2中求出的环的长度
     *
     * @param head
     * @return
     */
    private static int LinkLength(Node head) {
        int length = 0;
        if (head == null || head.next == null || head.next.next == null) {
            return length;
        }
        Node slow = head.next;
        Node fast = head.next.next;
        boolean flag = false;
        while (fast.next != null && fast.next.next != null) {
            if (slow == fast) {
                if (flag) {
                    break;
                } else {
                    flag = true;
                }
            }
            if (flag) {
                length++;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        if (!flag) {
            return length;
        }
        while (true) {
            if (head == slow) {
                return length;
            }
            length++;
            head = head.next;
            slow = slow.next;
        }
    }
}
